
// n个阶梯 一次可以上 1 阶，2 阶，3 阶

// 问有有几种方式走完阶梯

// 解：假如以f(n)表示方式

//n = 1    f(1) = 4
//n = 2    f(2) = 8

//n = k;
//第一步是：1 则剩下的有f(n-1)
//第二步是: 2 则剩下的有f(n-2)
//第三步是: 3 则剩下的有f(n-3)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<sys/time.h>
#include<time.h>
// 重复的递归与循环相差很大
// 递归
long int ladder(long int n){
    if(n == 1){
        return 1;
    }else if(n == 2){
        return 2;
    }else if(n == 3){
        return 4;
    }
    return ladder(n - 1) + ladder(n - 2) + ladder(n - 3);
}

// 循环
long int ladder2(long int n){
    if(n == 1){
        return 1;
    }else if(n == 2){
        return 2;
    }else if(n == 3){
        return 4;
    }
    long int n1 = 1,n2 = 2,n3 = 4;
    long int sum = 0;
    while(n >= 4){
        sum = n1 + n2 + n3;
        n1 = n2;
        n2 = n3;
        n3 = sum;
        n--;
    }
    return sum;
}

int
main(int argc,char * argv[]){

    struct timeval beginTime;
    struct timeval endTime;
    float timeRes1,timeRes2;
    int i = 0;
    const int count = 30;
    for(i = 1; i <= 20; ++i){

        int index = 0;
        long int sum = 0;
        
        gettimeofday(&beginTime,NULL);
        for(index = 1; index <= count; index++){

            sum = ladder(index);
        }
        gettimeofday(&endTime,NULL);
        timeRes1 = (endTime.tv_sec - beginTime.tv_sec) + 1e-6 * (endTime.tv_usec - beginTime.tv_usec);
        printf("index = %d . result1 = %ld, time = %f.\n",i,sum,timeRes1);

        sum = 0;
        gettimeofday(&beginTime,NULL);
        for(index = 1; index <= count; index++){

            sum = ladder2(index);
        }
        gettimeofday(&endTime,NULL);
        timeRes2 = (endTime.tv_sec - beginTime.tv_sec) + 1e-6 * (endTime.tv_usec - beginTime.tv_usec);
        printf("index = %d . result2 = %ld, time = %f.\n",i,sum,timeRes2);
    }
    return EXIT_SUCCESS;
}